/*
 * @lc app=leetcode.cn id=28 lang=javascript
 *
 * [28] 实现 strStr()
 */

// @lc code=start
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
 function buildNext(P) { // 构造模式串 P 的 next 表
  let m = P.length, j = 0; // “主”串指针
  let N = []; // next 表
  let t = N[0] = -1; // 模式串指针
  while (j < m - 1) {
    // 匹配
    if ( 0 > t || P[j] == P[t]) {
      j++; t++;
      N[j] = t; // 此句可改进为 N[j] = (P[j] != P[t] ? t : N[t]);
    }else {
      // 失配
      t = N[t];
    }
  }
  return N;
}
var strStr = function(haystack, needle) {
  if (needle === '') return 0
  let next = buildNext(needle); // 构造 next 表
  let n = haystack.length
  let m = needle.length
  let i = 0
  let j = 0
  while (i < n && j < m) {
    if (j < 0 || haystack[i] === needle[j]) {
      i++
      j++
    } else {
      j = next[j]
    }
  }
  if (j < m) return -1
  return i - j
};
// @lc code=end

